The present disclosure relates to determining translation maps to purge from memory. In particular, the present disclosure describes selecting which translation maps to page-out to flash for good paging efficiency. Still more particularly, the present disclosure relates to efficiently preserving the frequently used translation maps in memory to enable faster lookups.
Many storage device and systems use a dynamic translation table that keeps track of latest mapping of a logical block to physical media. As and when logical blocks are overwritten, the translation table is updated to point to the new physical media location and the old physical media location is reclaimed by garbage collection process. Example of such devices and systems include flash based SSDs, SMR drives, key-value and object stores, etc.
As device capacities increase, and also when data reduction (e.g.: compression and deduplication) techniques are active, the number of logical blocks (user data) that can be stored on the device increases, hence increasing the memory consumption of translation structures. In such systems, a paged translation system is implemented to constrain the memory consumption. A paged translation system stores a subset of translation table entries on the storage media with dynamic ‘page-in’ and ‘page-out’ of translation table entries depending on data access pattern. The performance on such systems is heavily influenced by the algorithms used to decide which subset of translation table entries must be resident in memory and which subset must go to storage media.
Not all translation table entries are spatially or temporally related and may not belong to a single namespace, partition, etc. Depending on input/output workload and the translation table entry access-pattern, some translation table entries are more likely to be accessed frequently and in near future than others. This presents a need to differentiate between the maps that are more useful to keep in memory and the ones that are not as useful.